package com.berchen.查找;

/**
 * 插值查找
 * 和二分查找相似 只是mid的计算方式不同
 */
public class InterpolationSearch {
    public static void main(String[] args){

//        int arr[]={1,2,4,6,6,6,6,6,7,8,10};
        int arr[]={1,5,6,9,10,43,54};
        int i = interpolation(arr, 54);
        System.out.println(i);
    }

    /**
     * 插值查找
     * @param arr
     * @param value
     */
    public static int interpolation(int[] arr,int value){

        int left=0;
        int right=arr.length-1;
        int mid=0;
        while (true){
            // value<arr[0] value>arr[arr.length-1] 确保mid不会越界
            if(left>right||value<arr[0]||value>arr[arr.length-1]){
                return -1;
            }
            mid=left+(value-arr[left])*(right-left)/(arr[right]-arr[left]);
            if(arr[mid]<value){
                left=mid+1;
            }
            if(arr[mid]>value){
                right=mid-1;
            }
            if(arr[mid]==value){
                return mid;
            }
        }
    }
}
